package fun.ticsmyc.dataStructure;

import java.util.*;

/**
 * @author Ticsmyc
 * @package fun.ticsmyc.dataStructure
 * @date 2020-07-27 21:17
 */
public class 单调栈 {

    //leetcode 496  下一个更大的元素1
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer,Integer> map = new HashMap<>();
        Deque<Integer> stack = new LinkedList<>();
        int[] res = new int[nums2.length];
        //从后往前
        for(int i=nums2.length-1 ; i>=0; --i){
            while(!stack.isEmpty() && nums2[i] > stack.peek()){
                stack.pop();
            }
            res[i] = stack.isEmpty() ? -1:stack.peek();
            map.put(nums2[i],res[i]);
            stack.push(nums2[i]);
        }
        int[] ans = new int[nums1.length];

        for(int i=0;i< nums1.length ; ++i){
            ans[i]=map.containsKey(nums1[i])? map.get(nums1[i]) :-1;
        }
        return ans;
    }

    // leetcode 503  下一个更大的元素2
    public int[] nextGreaterElements(int[] nums) {

        int[] res = new int[nums.length];
        Arrays.fill(res,-1);

        Deque<Integer> queue = new LinkedList<>();
        // 从前往后
        for(int i=0 ;i < nums.length*2; ++i){
            while(!queue.isEmpty() && nums[i%nums.length]>nums[queue.peek()]){
                res[queue.pop()] = nums[i%nums.length];
            }
            if(i<nums.length) {
                queue.push(i);
            }
        }
        return res;
    }
}
